1. Field of the Invention
The invention relates to a method and an assemblage for monitoring an output of a random generator.
2. Description of the Related Art
Random numbers, which are referred to as the outcome of random elements, are required for many applications. So-called “random generators” are used to generate random numbers. Random generators are methods that supply a sequence of random numbers. A crucial criterion for random numbers is whether the outcome of the generation can be regarded as independent of previous outcomes.
Random numbers are required, for example, for cryptographic methods. These random numbers are used, for example, to generate keys for encoding methods. Such keys are subject to stringent requirements in terms of randomness properties. Pseudo-random number generators (PRNGs), represented e.g. by a linear feedback shift register (LFRS), are therefore not suitable for this purpose. Only a true random number generator (TRNG) meets the applicable requirements. These utilize natural noise processes in order to obtain an unpredictable outcome. Noise generators that utilize the thermal noise of resistors or semiconductors, or the shot noise at potential barriers, for example at p-n transitions, are usual. A further possibility is to utilize the radioactive decay of isotopes.
While the “classic” methods use analog elements, such as e.g. resistors, as noise sources, digital elements such as, for example, inverters, have often been used in the recent past. These have the advantage of lesser complexity in terms of circuit layout, since they are available as standard elements.
It is known, for example, to use ring oscillators, which represent an electronic oscillator circuit. With these, an odd number of inverters is interconnected into a ring, producing an oscillation having a natural frequency. The natural frequency depends on: the number of inverters in the ring; the properties of the inverters; the interconnection conditions, i.e. lead capacitances; the operating voltage; and the temperature. The noise of the inverters results in a random phase shift with respect to the ideal oscillator frequency, which is used as a random process for the TRNG. It is noteworthy that ring oscillators oscillate independently, and do not require external components such as, for example, capacitors or coils.
One problem in terms of the utilization of randomness occurs because the ring oscillator must be sampled as close as possible to an expected ideal edge so that a random sample value is obtained. The publication of Bock, H., Bucci, M., Luzzi, R.: An Offset-Compensated Oscillator-Based Random Bit Source for Security Applications, CHES 2005, indicates a possibility for always sampling in the vicinity of an oscillator edge, by controlled shifting of the sampling point in time.
Published European patent document EP 1 686 458 B1 discloses a method for generating random numbers with the aid of a ring oscillator, in which a first and a second signal are made available, the first signal being sampled in a manner triggered by the second signal. In the method described, a ring oscillator is repeatedly sampled, in which context only non-inverting delays, i.e. an even number of inverters as delay elements, are always used. The oscillator ring is always sampled, simultaneously or with a mutual delay, after an even number of inverters beginning from a starting point. Shifting of the sampling time can thereby be omitted; instead, the repeatedly sampled signals are evaluated.
A further possibility involves the use of multiple ring oscillators, as explained, e.g., in the publication Sunar, B. et al.: “A Provable Secure True Random Number Generator with Built In Tolerance to Active Attacks,” IEEE Trans. on Computers, January 2007. Here multiple sample values from different ring oscillators are combined with one another and evaluated. A good random value can be achieved in this manner if the corresponding prerequisites in terms of implementation are met. Unfortunately the necessary XOR instruction cannot operate at the required high frequency, and because of substrate coupling on the chip the multiple ring oscillators are not independent of one another; they potentially correlate in terms of frequency (which, if applicable, is harmless), but also in terms of phase, with the result that it may not be possible to achieve the desired quality of the random numbers that are generated.
It should be noted that the complexities of known circuits according to the existing art are very substantial. Either a structure for shifting the sampling point in time must be used, which structure can moreover also be susceptible to attacks and make the generated bits dependent on one another; or a very large number of sample values must be processed in parallel. Additional delay elements may also be necessary. An additional, slow ring oscillator is furthermore required.
It is necessary in any event to monitor the output of the random generator in order to be able to identify whether the random generator is in fact supplying random output values.